/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._46;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 *
 * 给定一个没有重复数字的序列，返回其所有可能的全排列。
 *
 * 示例:
 *
 * 输入: [1,2,3]
 * 输出:
 * [
 *   [1,2,3],
 *   [1,3,2],
 *   [2,1,3],
 *   [2,3,1],
 *   [3,1,2],
 *   [3,2,1]
 * ]
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._46
 * @ClassName: Permutations
 * @Author: linyaonan
 * @Date: 2020/1/21 15:15
 */
public class Permutations {
    List<List<Integer>> result;
    int[] n;
    public List<List<Integer>> permute(int[] nums) {
        result = new ArrayList<>();
        n = nums;
        List<Integer> addNums = new ArrayList<>();
        for (int num : nums) {
            addNums.add(num);
        }
        List<Integer> add = new ArrayList<>();
        backTracing(addNums, add);
        return result;
    }

    private void backTracing(List<Integer> nums ,List<Integer> add) {
        if (add.size() == n.length) {
            List<Integer> temp = new ArrayList<>();
            temp.addAll(add);
            result.add(temp);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            Integer remove = nums.remove(i);
            add.add(remove);
            // 递归
            backTracing(nums, add);
            // 回溯
            nums.add(i, remove);
            add.remove(add.size() - 1);
        }
    }
}
